// APS105 Assignment 5 Starter Code
// Jonathan Deber (deberjon) 991234567

// This program helps solve a largest subset problem

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

/* The maximum number of numbers in our subsets. */
#define MAX_NUMBER_OF_NUMBERS 10

/* Yes and no responses. */
#define Y 'y'
#define N 'n'

/* Default number list to save typing. */
const int DEFAULT_NUMBERS[] = {1, 2, 4, 5, 8, 12, 15, 21};

/* Size of the default number list. */
const int NUM_DEFAULT_NUMBERS = sizeof(DEFAULT_NUMBERS) / sizeof(DEFAULT_NUMBERS[0]);

/* The struct used for the linked list Nodes. */
typedef struct node
{
    int numbers[MAX_NUMBER_OF_NUMBERS]; // The numbers that make up this subset
    int n;                              // The number of elements in 'numbers'
    
    struct node *next;                  // Pointer to the next node
} Node;


/* Node functions. */

/* Creates a new Node, and returns a pointer to it.
 * Copies 'n' and every value in 'numbers' into the equivalent fields in the new Node.
 * Sets the Node's 'next' pointer to NULL.
 * Nodes must be cleaned up with destroyNode(). 
 * Note: this function may be implemented iteratively. */
Node *createNode(const int numbers[], int n);

/* Cleans up the specified Node by free()ing any necessary fields, and then free()ing
 * the Node itself.  Does nothing if passed NULL. */
void destroyNode(Node *node);

/* Prints out the contents of the Node in the format specified in the assignment handout.
 * This function is used for debugging purposes, and is not used to print out the final answers. */
void debugPrintNode(const Node *node);

/* Returns the sum of all of the numbers in node->numbers.
 * Note: this function may be implemented iteratively. */
int calculateSumOfNode(const Node *node);



/* List functions. */

/* Creates a new Node containing 'numbers' and 'n', and adds it to the end of the linked 
 * list pointed to by 'head'.  Returns a pointer to the head of the list.  If 'head' is 
 * NULL, then we create a new list of size 1 (i.e., consisting entirely of the new Node we
 * just created), and return a pointer to that. 
 * Note: this function must be implemented recursively. */
Node *addNodeToList(Node *head, const int numbers[], int n);

/* Adds the linked list pointed to by 'head2' on to the end of the linked list pointed to by
 * 'head1'.  If 'head1' is NULL, returns 'head2'.  If 'head2' is NULL, then 'head1' is unchanged.
 * Note: this function must be implemented recursively. */
Node *addLists(Node *head1, Node *head2);

/* Prints out the list pointed to by 'head' in the format specified in the assignment handout. 
 * This function is used for debugging purposes, and is not used to print out the final answers.
 * Note: this function must be implemented recursively. */
void debugPrintList(const Node *head);

/* Prints out each set of numbers in the linked list pointed to by 'head', one per line.  This is used
 * to print out the final list of suggested subsets of numbers.
 * Note: this function must be implemented recursively. */
void printList(const Node *head);

/* Traverses the linked list pointed to by 'head', and determines the largest sum of the subset
 * in a Node that is less than or equal to 'targetValue'.
 * This function merely returns the sum, it does not return the subset itself.
 * Note: this function must be implemented recursively. */
int findHighestValidTotal(const Node *head, int targetValue);



/* Permutation functions. */

/* Generates all of the possible permutations (including permutations of 
 * shorter subsets) of the numbers in 'numbers' (which is of length 'n'), and returns them as a linked
 * list of Nodes.  The Nodes in the returned list must later be free()ed by
 * destroyNode(). */
Node *generatePermutations(const int numbers[], int n);

/* Generates all of the possible permutations that can be created by inserting 'number' 
 * into every element in the linked list pointed to by 'head', and returns
 * them as a new linked list. The Nodes in the returned list must later be free()ed
 * by destroyNode(). */ 
Node *insertIntoEveryElement(const Node *list, int number);




/*
 * Begin Changes Here.
 */
     
// Add any additional helper function prototypes or constants here.
// Helper function for step 3
void printNodeNumbers(const Node *node);

/*  Here I wrote a helper recursive function to find the last node of a list */
Node *findLastNode(Node *head);

Node *filterListwithSumValue(Node *head, int sumValue);

//cleanup all memories occupied by the nodes of a list
void freeList(Node *head);
/*
 * End Changes Here.
 */



/* True to print out additional debugging info, false to suppress it. */
#define DEBUGGING false


#ifndef AUTOMARKER /* Do *not* modify or delete this line of code; it is used by the auto-marker. */
int main(void)
{    
    /* The available numbers we have to work with. */
    int availableNumbers[NUM_DEFAULT_NUMBERS];
    
    /* The number of numbers in that array. */
    int numAvailableNumbers;
   
    // Ask the user if we want to use the default numbers
    char response;
    do
    {
        printf("Use default set of numbers? [y/n] ");
        scanf("%c", &response);
    } while (response != Y && response != N);
    
    // If so, copy in the default set
    if (response == Y)
    {
        for (int i = 0; i < NUM_DEFAULT_NUMBERS; i++)
        {
            availableNumbers[i] = DEFAULT_NUMBERS[i];
        }
        numAvailableNumbers = NUM_DEFAULT_NUMBERS;
    }
    // Otherwise, prompt the user for numbers
    else
    {
        int number = 0;
        numAvailableNumbers = 0;
        for (int i = 0; i < MAX_NUMBER_OF_NUMBERS && number != -1; i++)
        {
            printf("Enter a number (-1 to exit): ");
            scanf("%d", &number);
            
            if (number != -1)
            {
                availableNumbers[i] = number;
                numAvailableNumbers++;
            }
        }
    }

    // Prompt the user for a target value    
    int targetValue;
    printf("Enter target value: ");
    scanf("%d", &targetValue);
    
	/*  testing linked list */
	int a1[] = {2,3,4};
	int a2[] = {2,3};
	int a3[] = {4};

	Node *n0 = createNode(a1, 3);
	Node *n1 = createNode(a2, 2);
	Node *n2 = createNode(a3, 1);

	debugPrintNode(n0);

	addNodeToList(n0, a2, 2);

	debugPrintList(n0);

	addLists(n0, n2);

	debugPrintList(n0);

	/*  testing insertIntoEveryElement function */
	Node *n3 = insertIntoEveryElement(n0, 10);

	debugPrintList(n0);
	debugPrintList(n3);

	/*  testing generatePermutations function */
	printf("Testing generatePermutations function\n");
	Node *n4 = generatePermutations(a1, 3);

	debugPrintList(n4);

	printf("Testing findHighestValidTotal function\n");
	printf("Bigest value is %d\n", findHighestValidTotal(n4, 2));

	destroyNode(n0);
	destroyNode(n1);
	destroyNode(n2);


    /*
     * Begin Changes Here (Steps 10, 11, 12, 13, 14).
     */
        
    // Generate the set of possible permutations.
	Node *allSubsets = generatePermutations(availableNumbers, numAvailableNumbers);
    
    // Get the highest total less than or equal to targetValue.
	int highestTotal = findHighestValidTotal(allSubsets, targetValue);

    // Filter the list of permutations to get the subsets with that total.
	Node *filteredList = filterListwithSumValue(allSubsets, highestTotal);
    
    // Print out those filtered subsets
	printf("The subset(s) closest to the target value are:\n");
	printList(filteredList);

    // Clean up
	freeList(allSubsets);
	freeList(filteredList);
    
    /*
     * Begin Changes Here.
     */

    return 0;
}
#endif /* Do *not* modify or delete this line of code; it is used by the auto-marker. */



Node *createNode(const int numbers[], int n)
{
    /*
     * Begin Changes Here (Step 2).
     */ 
	Node *pNode = (Node *)malloc(sizeof(Node));

	pNode->n = n;
    /*  We can use iterative here */
	for(int i=0; i<n; i++)
	{
		pNode->numbers[i] = numbers[i];
	}

	pNode->next = NULL;

    return pNode;  // REPLACE THIS LINE
        
    /*
     * End Changes Here.
     */ 
}

void destroyNode(Node *node)
{
    /*
     * Begin Changes Here (Step 2).
     */

	free(node);
    
    /*
     * End Changes Here.
     */ 
}

void debugPrintNode(const Node *node)
{
    /*
     * Begin Changes Here (Step 3).
     */
    if(node==NULL)
	{
		printf("  [null]\n");
	} 
	else
	{
		printf("----------\n");
		printf("Numbers: ");
		
		printNodeNumbers(node);
		
		printf("n: %d\n", node->n);
		printf("----------\n");
	}
    
    /*
     * End Changes Here.
     */
}


int calculateSumOfNode(const Node *node)
{
    /*
     * Begin Changes Here (Step 11).
     */
	int sum=0;
    for(int i=0; i<node->n; i++)
		sum+=node->numbers[i];

    return sum;  // REPLACE THIS LINE
    
    /*
     * End Changes Here.
     */
}




Node *addNodeToList(Node *head, const int numbers[], int n)
{
    /*
     * Begin Changes Here (Step 5).
     */
	Node *node = createNode(numbers, n);

	Node *lastNode = findLastNode(head);

	lastNode->next = node;
	node->next = NULL;

    return head;  // REPLACE THIS LINE
    
    /*
     * End Changes Here.
     */
}

Node *addLists(Node *head1, Node *head2)
{
    /*
     * Begin Changes Here (Step 6).
     */
	if (head1 == NULL)
		return head2;

	if (head2 == NULL)
		return head1;

	// if reach here, list1 and list2 all not NULL
	Node *list1LastNode = findLastNode(head1);
	list1LastNode->next = head2;

    return head1;  // REPLACE THIS LINE
      
    /*
     * End Changes Here.
     */
}


void debugPrintList(const Node *head)
{
    /*
     * Begin Changes Here (Step 4).
     */
	Node* nextNode;

	if(head==NULL)
	{
		debugPrintNode(head);
		return;
	}
	else
	{
		nextNode = head->next;
		debugPrintNode(head);
		printf("    |\n");
		printf("    v\n");
		debugPrintList(nextNode);
	}

    /*
     * End Changes Here.
     */
     
}

void printList(const Node *head)
{
    /*
     * Begin Changes Here (Step 13).
     */
	while( head != NULL)
	{
		printNodeNumbers(head);
		head = head->next;
	}
        
    /*
     * End Changes Here.
     */
}


int findHighestValidTotal(const Node *head, int targetValue)
{
    /*
     * Begin Changes Here (Step 11).
     */

	int mySum=0, othersSum=0, retSum=0;

    // If the list is empty, our sum is 0
    if(head == NULL)
	{
		retSum = 0;
	}
	else // Otherwise
	{
        // Calculate the sum of this node
		mySum = calculateSumOfNode(head);
        
        // Is it in range?
		if(mySum <= targetValue)
			retSum = mySum; 

        // Calculate the largest valid sum in the rest of the list        
		othersSum = findHighestValidTotal(head->next, targetValue);

        // Is that bigger than this Node's sum?        
		if(othersSum > mySum || mySum>targetValue)
			retSum = othersSum;
	}
    
	printf("=====================================\n");
	debugPrintNode(head);
	printf("mySum(%d)vs othersSum(%d), retSum = %d\n", mySum, othersSum, retSum);

    return retSum;  // REPLACE THIS LINE
    
    /*
     * End Changes Here.
     */
}



Node *generatePermutations(const int numbers[], int n)
{
    /*
     * Begin Changes Here (Step 8).
     */
     
    // Print out some information about the function call
    // (This debugging info may be printed iteratively)
    if (DEBUGGING)
    {

    }
    
    /* Create a linked list to hold our permutations. */
	Node *retList = NULL;
    
    // If we're down to a single number, add it as a 1-item subset and stop recursing.
	if(n==1)
	{
		retList = addLists(retList, createNode(numbers, n));
	}
	else //Otherwise
	{
        // Take off the first number.
        // Generate all of the permutations of the smaller subset.
		Node *subList = generatePermutations(&numbers[1], n-1);
        
        // Insert the removed number into every subset in that list.
		retList = addLists(retList, insertIntoEveryElement(subList, numbers[0]));
        
        // Add on the subsets we obtained from the recursive call.
		retList = addLists(retList, subList);
        
        // Add on a subset containing our single number.
		retList = addLists(retList, createNode(numbers, 1));

	}    
    return retList;  // REPLACE THIS LINE
    
    /*
     * End Changes Here.
     */
}

Node *insertIntoEveryElement(const Node *head, int number)
{    
    /*
     * Begin Changes Here (Step 9).
     */
         
    // Print out some information about the function call
    // (This debugging info may be printed iteratively)
    if (DEBUGGING)
    {

    }
    
    // if head == NULL, return value will be NULL
	// otherwise, it will return an address pointing to heap
	Node *clonedNode = NULL;

    // As long as there are still Nodes in the list, keep processing.
	if(head != NULL)
	{
        // Create a new Node with the existing numbers and the single number.
		clonedNode = createNode(head->numbers, head->n+1);
		clonedNode->numbers[head->n] = number;
        // Recursively generate all of the insertions for the remaining Nodes.
		clonedNode->next = insertIntoEveryElement(head->next, number);
	}

    return clonedNode;  // REPLACE THIS LINE
    
    /*
     * End Changes Here.
     */
}







/*
 * Begin Changes Here.
 */
     
// Place any new helper functions here.
//
/*  helper function for step 3 to print all numbers  */
void printNodeNumbers(const Node *node)
{
	for(int i=0; i<node->n; i++)
		printf("%d ", node->numbers[i]);

	printf("\n");
}

/*  Here I wrote a helper recursive function to find the last node of a list */
Node *findLastNode(Node *head)
{
	if(head->next == NULL)
		return head;

	//recursive part
	return findLastNode(head->next);
}


/*  It didn't say we can't use iterative way here, so I just use iterative way */
Node *filterListwithSumValue(Node *head, int sumValue)
{
	Node *retNode = NULL;
	
	while(head != NULL)
	{
		if (calculateSumOfNode(head) == sumValue)
			retNode = addLists(retNode, createNode(head->numbers, head->n));

		head = head->next;
	}

	return retNode;
}

void freeList(Node *head)
{
	if(head==NULL)
		return;

	Node *tmpNode = head->next;
	destroyNode(head);
	freeList(tmpNode);
}

/*
 * End Changes Here.
 */ 

